//给定一个整数 n ，返回 n! 结果中尾随零的数量。 
//
// 提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：0
//解释：3! = 6 ，不含尾随 0
// 
//
// 示例 2： 
//
// 
//输入：n = 5
//输出：1
//解释：5! = 120 ，有一个尾随 0
// 
//
// 示例 3： 
//
// 
//输入：n = 0
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= n <= 10⁴ 
// 
//
// 
//
// 进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？ 
// Related Topics 数学 👍 581 👎 0

package leetcode.editor.cn;

public class _172_FactorialTrailingZeroes {
    public static void main(String[] args) {
        Solution solution = new _172_FactorialTrailingZeroes().new Solution();
        int n = 30;
        System.out.println(solution.trailingZeroes(n));
    }

    class Solution {
        public int trailingZeroes(int n) {
            int res = 0;
            while (n > 0) {
                res += n / 5;
                n /= 5;
            }
            return res;
        }
    }

    // 官方给的方法，还可以优化
    class Solution2 {
        public int trailingZeroes(int n) {
            int res = 0;
            for (int i = 1; i <= n; i++) {
                int N = i;
                while (N > 0) {
                    if (N % 5 == 0) {
                        res++;
                        N /= 5;
                    } else {
                        break;
                    }
                }
            }
            return res;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 溢出了
    class Solution1 {
        int cnt;

        public int trailingZeroes(int n) {
            cnt = 0;
            process(n);

            return cnt;
        }

        private long process(long n) {
            if (n == 0) {
                return 0;
            } else if (n == 1) {
                return 1;
            } else {
                long tmp = n * process(n - 1);
                if (tmp % 10 == 0) {
                    cnt++;
                    tmp /= 10;
                }
                return tmp;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}